/**
 * Straight implementation.
 * 
 * Go through bi-directional on the same time.
 * When the two characters are both '?', then add the smaller cost of oCost and xCost.
 * When the one of two characters is '?', then add the corresponding cost.
 * When none of them are '?', check if they are in the same character.
 */

/**
 * @author antonio081014
 * @since Dec 28, 2011, 8:17:29 AM
 */

public class MinCostPalindrome {
	public int getMinimum(String s, int oCost, int xCost) {
		int cost = 0;
		for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
			if (s.charAt(i) == '?' && s.charAt(j) == '?')
				cost += 2 * Math.min(oCost, xCost);
			else if (s.charAt(i) == '?')
				cost += (s.charAt(j) == 'x' ? xCost : oCost);
			else if (s.charAt(j) == '?')
				cost += (s.charAt(i) == 'x' ? xCost : oCost);
			else if (s.charAt(i) != s.charAt(j))
				return -1;
		}
		return cost;
	}
	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
